package com.tgy.algorithm.base._滑动窗口;

import java.util.LinkedList;

/**
 * 给定一个整型数组arr，和一个整数num
 * 某个arr中的子数组sub，如果想达标，
 * 必须满足sub中最大值-sub中最小值<=num,返回arr中达标子数组的数量
 */
public class _查找数组中子数组最大值与最小值相距的数量_01 {

    public static int getDistanceSubArr(int[] nums,int distance) {

        int len = nums.length;
        if (nums == null || len == 0 || distance < 0) {
            return 0;
        }

        int count = 0;

        LinkedList<Integer> minQueue = new LinkedList<>();
        LinkedList<Integer> maxQueue = new LinkedList<>();

        int value = 0;
        int right = 0;
        for (int i = 0; i < len; i++) {
            while (right < len) {
                value = nums[right];
                while (!minQueue.isEmpty() && nums[minQueue.peekLast()] >= value) {
                    minQueue.pollLast();
                }
                minQueue.offerLast(right);

                while (!maxQueue.isEmpty() && nums[maxQueue.peekLast()] <= value) {
                    maxQueue.pollLast();
                }
                maxQueue.offerLast(right);

               if (nums[maxQueue.peekFirst()]  -  nums[minQueue.peekFirst()] > distance) {
                   break;
               }else {
                   right++;
               }
            }

            count += (right - i);
            if(maxQueue.peekFirst() == i) {
                maxQueue.pollFirst();
            }

            if (minQueue.peekFirst() == i) {
                minQueue.pollFirst();
            }
        }

        return count;
    }

    public static void main(String[] args) {
        // 2 3 4 1 5 6    == 2
        int s = getDistanceSubArr(new int[]{2, 3, 4, 1, 5, 6}, 2);
        System.out.println(s);
    }
}
